Having established the logic of the partition function, let's execute a step-by-step trace to see how its two-pointer technique works. The goal is to place the pivot element $P$ in its final sorted position, dividing the array $A$ for recursive calls.

  • The key to the in-place Lomuto scheme is the index $i$, which strictly maintains the boundary of the 'smaller than pivot' region.
  • If the iterator $j$ finds an element $A[j]$ that is $\leq P$, we must expand that smaller region by incrementing $i$ and swapping $A[i]$ and $A[j]$.
  • This swap guarantees that $A[i]$ (the element now at the boundary) belongs in the small partition.
  • The final step is swapping the pivot into position $i+1$, effectively completing the $O(n)$ partitioning phase.
  • Partitioning Result Structure: The function transforms a segment $A[low..high]$ into three distinct regions: $$A[low \dots i] \mid P \mid A[i+2 \dots high]$$
    • Left Region: Contains elements guaranteed to be $\leq P$.
    • Right Region: Contains elements guaranteed to be $> P$.
    • The function returns the final index of the pivot, $i+1$.